package medium;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/6/5 15:47
 */
public class No91_解码方法 {
    public static void main(String[] args) {
        Solution91 solution91 = new Solution91();
        int res = solution91.numDecodings("00");
        System.out.println(res);
    }
}

class Solution91 {
    public int numDecodings(String s) {
        //2231  2,23,1   22,3,1  2,2,31???x
        
        //爬楼梯,每次上1个,或者2个台阶,一共多少种???
        //动态规划
        
        // 1206 1,20,6
        int length = s.length();
        if (length == 1) {
            return s.charAt(0) == '0' ? 0 : 1;
        }
        //定义dp[n]为n位字符串拆成的组合数
        int[] dp = new int[length + 1];
        
        //难点:初始化dp[1] dp[2]
        //dp[1] 0    1-9
        if (s.charAt(0) == '0') {
            dp[1] = 0;
        } else {
            dp[1] = 1;
        } 
        
        //dp[2] 如何计算 
        char one = s.charAt(0);
        char two = s.charAt(1);
        //如果是00 ,肯定是0
        if (one == '0' && two == '0') {
            dp[2] = 0;
        } else if (one == '0' && two != '0') {
            dp[2] = 0;
        } else if (one != '0' && two == '0') {
            String base = one + "" + two;
            if ("10".equals(base) || "20".equals(base)) {
                dp[2] = 1;
            } else {
                dp[2] = 0;
            }
        } else {
            // 26 27
            //26 2
            //27 1
            String base = one + "" + two;
            if (Integer.valueOf(base) > 26) {
                dp[2] = 1;
            } else {
                dp[2] = 2;
            } 
        } 
        
        //以上坚强分析,将dp[2]初始化成功
        
        
        //状态的转移
        //dp[n] = dp[n-1] + 1位
        //dp[n] = dp[n-2] + 2位

        for (int i = 3; i <= length; i++) {
            //首先 dp[n-1] + 1位
            char 前 = s.charAt(i - 2);
            char 后 = s.charAt(i - 1);
            String check = 前 + "" + 后;
            
            //dp[n-1]
            if (后 == '0') {
                //说明不能进来,就是0
                dp[i] += 0;
            } else {
                dp[i] += dp[i - 1];
            } 
            
            // dp[n-2] + 2位 不能破坏集合
            //同时注意 2位要整体,不要拆开,否则掉坑!!!!
            if (前 != '0' && Integer.valueOf(check) <= 26) {
                //有效
                dp[i] += dp[i - 2];
            }
        }

        return dp[length];

    }

}





